package com.fps.webshop.question.question0200_0299;

import com.fps.webshop.question.common.ListNode;

/**
 * 206. 反转链表
 * 
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * 
 * 示例 1：
 * Question206_01.jpg
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 * 
 * 示例 2：
 * Question206_02.jpg
 * 输入：head = [1,2]
 * 输出：[2,1]
 * 
 * 示例 3：
 * 输入：head = []
 * 输出：[]
 * 
 * 提示：
 * 		链表中节点的数目范围是 [0, 5000]
 * 		-5000 <= Node.val <= 5000
 * 
 * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
 */
public class Question206 {
	
	/**
	 * 第一次提交，链表遍历循环，还行
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	38.3 MB	Java	2021/08/17 16:00
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：38.3 MB, 在所有 Java 提交中击败了31.50%的用户
	 */
	public static ListNode reverseList1(ListNode head) {
		ListNode start = null;
		ListNode endNode = null;
		while(head!=null) {
			if(endNode==null) {
				ListNode tmp = head.next;
				endNode = head;
				endNode.next=null;
				start = head;
				head = tmp;
			}else {
				ListNode tmp = head.next;
				start = head;
				start.next = endNode;
				endNode = start;
				head = tmp;
			}
		}
		return start;
    }
	/**
	 * 第二次提交，优化代码
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	38.2 MB	Java	2021/08/17 16:03
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：38.2 MB, 在所有 Java 提交中击败了53.10%的用户
	 */
	public static ListNode reverseList2(ListNode head) {
		ListNode endNode = null;
		while(head!=null) {
			if(endNode==null) {
				ListNode tmp = head.next;
				endNode = head;
				endNode.next=null;
				head = tmp;
			}else {
				ListNode tmp = head.next;
				head.next = endNode;
				endNode = head;
				head = tmp;
			}
		}
		return endNode;
    }
	
	
	public static void main(String[] args) {
		ListNode l5 = new ListNode();
		l5.val = 5;
		l5.next=null;
		
		ListNode l4 = new ListNode();
		l4.val = 4;
		l4.next=l5;
		
		ListNode l3 = new ListNode();
		l3.val = 3;
		l3.next=l4;
		
		ListNode l2 = new ListNode();
		l2.val = 2;
		l2.next=l3;
		
		ListNode l1 = new ListNode();
		l1.val = 1;
		l1.next=l2;
		
		ListNode l = reverseList1(l1);
		while(l.next!=null) {
			System.out.print(l.val+" ");
		}
	}
}
